class Solution9 {
    public static void main(String[] args) {
        int[] nums1 = {1, 4, 6, 9};
        int[] nums2 = {2, 5, 7, 8};
        merge(nums1, nums1.length, nums2, nums2.length);

    }
    /*

    解题思路:

      1. 从后往前遍历数组，将nums1和nums2中的元素逐个比较

         将较大的元素往nums1末尾进行搬移

      2. 第一步结束后，nums2中可能会有数据没有搬移完，将nums2中剩余的元素逐个搬移到nums1

 */


    public static void merge(int[] nums1, int m, int[] nums2, int n) {

        // end1、end2：分别标记nums1 和 nums2最后一个有效元素位置

        // end标记nums1的末尾，因为nums1和nums2中的元素从后往前往nums1中存放

        // ，否则会存在数据覆盖

        int end1 = m - 1;

        int end2 = n - 1;

        int end = nums1.length - 1;


        // 从后往前遍历，将num1或者nums2中较大的元素往num1中end位置搬移

        // 直到将num1或者num2中有效元素全部搬移完

        while (end1 >= 0 && end2 >= 0) {

            if (nums1[end1] > nums2[end2]) {

                nums1[end--] = nums1[end1--];

            } else {

                nums1[end--] = nums2[end2--];

            }

        }


        // 如果nums2中的数据没有搬移完，搬移剩余nums中的元素

        while (end2 >= 0) {

            nums1[end--] = nums2[end2--];

        }


        // num1中可能有数据没有搬移完，不用管，因为这些元素已经在nums1中了

    }

}
